COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00009 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a59.tex[106,phy] \today\hfill}

\bigskip

\line{\bf Maxima and Minima\hfil}
\line{\it ``The Best is the Enemy of the Good''\hfill}

A frequent task in computing is to find the best, for some purpose, of a
finite set.  If $f(i)$ is my predicted profit from making $i$~widgets this
year, and my factory can't make more than 1000 of them in a year, I~need to
know the value of $i$ between 1 and~1000 that makes $f(i)$ the largest.  I~may
also have more than a passing interest in the value $f(i)$ has for that value
of~$i$.

The \naive\ way to do the problem is to test each value of $i$ in turn, against
all the other numbers, printing~$i$ if it wins all these contests.  In
outline, here is the program:

{\obeylines\obeyspaces\let =\ \tt
        FOR I:=1 TO 1000 DO
            BEGIN
            LOSSES:=0;
            FOR J:=1 TO 1000 DO
                IF F(I)<F(J) THEN
                    LOSSES:=LOSSES+1;
            IF LOSSES=0 THEN
                WRITELN(I,F(I))
            END
}

\smallskip
This program has several problems.  It potentially prints several equally
good values of~$i$, though that isn't necessarily bad.  It takes far too much
time, executing some operations a million times when it could be
redesigned not to do anything more than a thousand times.  The faster
program is also shorter.

The problem with the program above is that it is conducting a contest among
the numbers from~1 to~1000 as if it were a round robin tournament, where
everyone plays a game against everyone else.  To find the best player using
the fewest games, it is far more efficient to use a knockout tournament,
where losers are eliminated from further play.  A~program can run through
the numbers from~1 to~1000, keeping track only of the current number, and of
that previous number that beat all the others.  Using a variable {\tt BESTSOFAR}
to keep the current winner, the program is:

{\obeylines\obeyspaces\let =\ \tt
        BEGIN
        BESTSOFAR:=1;
        FOR I:=2 TO 1000 DO
            IF F(I)>F(BESTSOFAR) THEN
                BESTSOFAR:=I;
        WRITELN(BESTSOFAR, F(BESTSOFAR))
        END.
}

\vfill\eject

A slight improvement in efficiency can be made by not discarding the best
value of~$f$ so far:

{\obeylines\obeyspaces\let =\ \tt
        BEGIN
        BESTSOFAR:=1;
        FBEST:=F(1);
        FOR I:=2 TO 1000 DO
            BEGIN
            FI:=F(I);
            IF FI>FBEST THEN
                BEGIN
                FBEST:=FI;
                BESTSOFAR:=I;
                END
            END
        END
}

\smallskip
The same pattern can, of course, be used to find the smallest, by changing
``$>$'' to~``$<''$.  We can find the first or last number that meets a condition by
similar programs.  Say we want to find the largest number between 1 and
1000 that meets a certain test.  Here are several methods:

{\obeylines\obeyspaces\let =\ \tt
{\rm{(1)}}     LARGEST:=0;
        FOR I:=1 TO 1000 DO
            IF TEST(I) THEN
                LARGEST:=I;
        IF I>0 THEN WRITELN(`LARGEST:' I)
        ELSE WRITELN(`NO NUMBER SATISFIES THE TEST')

{\rm{(2)}}     I:=1000;
        WHILE (I>0) AND NOT TEST(I) DO
            I:=I-1;
        IF I>0 THEN WRITELN(`LARGEST:' I)
        ELSE WRITELN(`NO NUMBER SATISFIES THE TEST')

{\rm{(3)}}     FOR I:=1000 DOWNTO 1 DO
        IF TEST(I) THEN
            BEGIN LARGEST:=I
            GO TO 99;
            END
        WRITELN(`NO NUMBER SATISFIES THE TEST');
        GO TO 100;
        99: WRITELN(`LARGEST:' LARGEST);
        100: END.
}




\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft March  28, 1984

\bye